package com.example.link;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2022/3/6
 * @Created by Jonathan
 */
public class FindFirstIntersectNode {

    private static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }

    // todo 这是一个德高望重的大哥
    // 给定两个可能有环也可能无环的单链表，头结点head1、head2
    // 请实现一个函数，如果两个链表相交，返回相交的第一个节点 如果不想交返回null
    // 1)两个无环链表相交的话 一最后一定是公共部分
    // 2)两个有环链表相交一定是共用环  这种情况下
    //      入环节点可能相同 入环节点是一个 那么就可以不看环了
    //      也可能不同


    //两个无环链表相交的话 一最后一定是公共部分
    //      -------- \
    //                --------------------
    // --------------/
    public static Node getIntersectNodeWithoutLoop(Node head1, Node head2) {
        Node cur1 = head1, cur2 = head2;
        int distance = 0;
        while (cur1 != null) {
            cur1 = cur1.next;
            distance++;
        }
        while (cur2 != null) {
            cur2 = cur2.next;
            distance--;
        }
        // distance>=0 cur1长 否则cur2长
        cur1 = head1;
        cur2 = head2;
        if (distance >= 0) {
            for (int i = 0; i < distance; i++) {
                cur1 = cur1.next;
            }
        } else {
            for (int i = 0; i < -distance; i++) {
                cur2 = cur2.next;
            }
        }
        // 后面的距离 现在都相等了
        while (cur1 != null && cur2 != null) {
            if (cur1 == cur2) return cur1;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return null;
    }


    @Test
    public void testGetIntersectNodeWithoutLoop() {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        node1.next = node2;
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        Node node8 = new Node(8);
        //Node node9 = new Node(9);
        //node8.next = node9;
        //node2.next = node8;
        //node7.next = node8;
        Node intersectNodeWithoutLoop = getIntersectNodeWithoutLoop(node1, node4);
        System.out.println(intersectNodeWithoutLoop);

    }


    // 单链表 判断是否有环
    // 快指针走两步 慢指针走一步  相遇之后 快指针回到开头
    // 快指针走一步 慢指针走一步 相遇点就是 第一个入环节点
    private static Node getLoopNode(Node head) {
        // 至少三个节点才能成环
        if (head == null || head.next == null || null == head.next.next)
            return null;
        Node slow = head.next /*慢指针*/, fast = head.next.next/*块指针*/;
        // 第一次while循环判断是否有环
        while (slow != fast) {
            // 快指针不为空
            // 如果fast.next为null的话 fast.next.next就会报空指针 这个判断需要加强一下
            if (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            } else {
                //快指针等于null 说明当前链表是无环的 直接返回null结束运行即可
                return null;
            }
        }
        fast = head; /*快指针从头结点从新开始*/
        // 第二次while循环找出一个入环的节点
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }


    private static Node create(List<Integer> list, Boolean loop) {
        Node head = new Node(list.get(0));
        Node cur = head;
        for (int i = 1; i < list.size(); i++) {
            cur.next = new Node(list.get(i));
            cur = cur.next;
            // 成环
            if (loop) {
                if (i == list.size() - 1) {
                    cur.next = head.next;
                }
            }
        }
        return head;
    }

    @Test
    public void testGetLoopNode() {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        list.add(8);
        Node node = create(list, true);
        Node node1 = create(list, false);
        System.out.println(getLoopNode(node));
        System.out.println(getLoopNode(node1));

        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);
        Node node2 = create(list1, false);
        Node node3 = create(list1, true);
        System.out.println(getLoopNode(node2));
        System.out.println(getLoopNode(node3));

    }


}
